package Leetcode第二期;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author : K k
 * @date : 10:46 2020/9/25
 * 根据一棵树的中序遍历与后序遍历构造二叉树。
 *
 * 注意:
 * 你可以假设树中没有重复的元素。
 *
 * 例如，给出
 *
 * 中序遍历 inorder = [9,3,15,20,7]
 * 后序遍历 postorder = [9,15,7,20,3]
 * 返回如下的二叉树：
 *
 *     3
 *    / \
 *   9  20
 *     /  \
 *    15   7
 */
public class 从中序与后序遍历序列构造二叉树_106 {

    //递归
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if(inorder.length==0 || postorder.length==0 || inorder.length!=postorder.length){return null;}
        TreeNode root=build(inorder,postorder,0,inorder.length-1,0,postorder.length-1);
        return root;
    }

    private TreeNode build(int[] inorder, int[] postorder, int left, int right, int postLeft, int postRight) {
        if(left<=right && postRight>=postLeft) {
            //查找分界点
            int rootIndex=left;
            for(int i=left;i<=right;i++){
                if (inorder[i]==postorder[postRight]){
                    rootIndex=i;
                    break;
                }
            }
            TreeNode root=new TreeNode(inorder[rootIndex]);
            root.left=build(inorder,postorder,left,rootIndex-1,postLeft,postLeft+(rootIndex-left)-1);
            root.right=build(inorder,postorder,rootIndex+1,right,postLeft+(rootIndex-left),postRight-1);
            return root;
        }
        return null;
    }

    //迭代
    public TreeNode buildTreeA(int[] inorder, int[] postorder) {
        if (postorder == null || postorder.length == 0) {
            return null;
        }
        TreeNode root = new TreeNode(postorder[postorder.length - 1]);
        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        stack.push(root);
        int inorderIndex = inorder.length - 1;
        for (int i = postorder.length - 2; i >= 0; i--) {
            int postorderVal = postorder[i];
            TreeNode node = stack.peek();
            if (node.val != inorder[inorderIndex]) {
                node.right = new TreeNode(postorderVal);
                stack.push(node.right);
            } else {
                while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) {
                    node = stack.pop();
                    inorderIndex--;
                }
                node.left = new TreeNode(postorderVal);
                stack.push(node.left);
            }
        }
        return root;
    }


    public static void main(String[] args) {
        从中序与后序遍历序列构造二叉树_106 x=new 从中序与后序遍历序列构造二叉树_106();
        TreeNode treeNode = x.buildTree(new int[]{1, 2, 3, 4}, new int[]{2, 3, 4, 1});
    }
}
